/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    using ListNode = Node;
    Node* copyRandomList(Node* head) {
        if (!head)
            return head;

        //在原链表的每个节点后面都插入一个相同值的节点，作为返回链表的节点
        for (ListNode* cur = head; cur; cur = cur->next->next)
        {
            ListNode* newNode = new ListNode(cur->val);
            newNode->next = cur->next;
            cur->next = newNode;
        }

        //a -> a` -> b -> b` -> c -> c`
        //这样，a`的random就是a->random->next
        for (ListNode* cur = head; cur; cur = cur->next->next)
        {
            ListNode* Next = cur->next;
            Next->random = cur->random ? cur->random->next : nullptr;
        }

        //恢复原链表，并将新链表的节点提取出来
        ListNode* retHead = head->next;
        for (ListNode* cur = head; cur; cur = cur->next)
        {
            ListNode* Next = cur->next;
            cur->next = cur->next->next;
            Next->next = Next->next ? Next->next->next : nullptr;
        }

        return retHead;
    }
};